// 题目链接：https://www.luogu.com.cn/problem/P2895

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define px first
#define py second
typedef pair<int, int> PII;

const int N = 305;

int m;
int dist[N][N];
int hit[N][N];
queue<PII> q;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

int BFS()
{
    q.push({0, 0});
    dist[0][0] = 0;

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int a = t.px + dx[i];
            int b = t.py + dy[i];

            if (a < 0 || b < 0)
                continue;
            if (dist[a][b])
                continue;
            if (dist[t.px][t.py] + 1 >= hit[a][b])
                continue;

            q.push({a, b});
            dist[a][b] = dist[t.px][t.py] + 1;

            if (hit[a][b] == 0x3f3f3f3f)
                return dist[a][b];
        }
    }
    return -1;
}

int main()
{
    int x, y, t;
    memset(hit, 0x3f, sizeof hit);
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d %d %d", &x, &y, &t);

        hit[x][y] = min(hit[x][y], t);

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i];
            int b = y + dy[i];

            if (a < 0 || a > 301 || b < 0 || b > 301)
                continue;

            hit[a][b] = min(hit[a][b], t);
        }
    }

    int res = BFS();
    printf("%d\n", res);

    return 0;
}